from typing import List


class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        # 方向
        op=[(0,1),(1,0),(0,-1),(-1,0)]
        mp=[[0]*n for _ in range(n)]
        i,j=0,0
        dx=0
        cnt=1
        for _ in range(n*n):
            mp[i][j]=cnt
            x,y=i+op[dx][0],j+op[dx][1]
            if x<0 or x>=n or y<0 or y>=n or mp[x][y] !=0:
                # 改变方向
                dx=(dx+1)%4
            i+=op[dx][0]
            j+=op[dx][1]
            cnt+=1
        return mp